import sys
import binascii

def bitcount(x):
	count=0
	if x<0:
		x= ~x + 1
	while x!=0:
		count+=x&1
		x=x>>1
	return count

# ans_string = Final ans string getting computed. It has characters the function is already considering. 
#	We will add new characters to this and pass it to a new invocation of append_and_check.
# n = Level of recursion
# diff = The highest bit difference between doc1 and appended doc2, found so far.
# doc1 - Document to be matched
# doc2 - Document to be appended to, to match doc1

def append_and_check(ans_string, n, diff, doc2, doc1):
	global lastString

	# Initializing to sentinel values
	cstring=''
	closest=-1

	# handling the base case of recursion here
	if n==1:
		for i in range(32,126):
			if diff==0:
				return diff,closest,cstring
			myans = ans_string
			myans = myans + str(chr(i))

			#actual processing
			ntext = doc2 + myans
			this_diff = bitcount(binascii.crc32(doc1) ^ binascii.crc32(ntext))

			if(this_diff < diff):
				diff=this_diff
				closest=binascii.crc32(ntext)
				cstring=ntext

				if this_diff==0:
					return diff,closest,cstring
		return diff,closest,cstring
	else:
		for i in range(32,126):
			if diff==0:
				return diff,closest,cstring
			myans = ans_string
			myans = myans + str(chr(i))
			d,c,cs = append_and_check(myans,n-1,diff,doc2,doc1)
			if d==0:
				return d,c,cs

			if(d<diff):
				diff=d
				closest=c
				cstring =cs
		return diff,closest,cstring

# startstring - The character which determines the search space for a process. If given 'a' here, the process 
#			only searches for strings starting with 'a'.
# doc2 - Document to be appended to
# doc1 - Document that has to be matched
# Length - What is the length of appended string that we want to search for. We first search for 
#			strings of length 1, then length 2 and so on.
#
def findmatch(startstring, doc2, doc1, length, requestID):
	#Initialization of sentinel values - If you see this in the output, something went wrong. Somewhere.
	diff=121212112313123123123

	diff,closest,cstring = append_and_check(startstring,length,diff,doc2,doc1)
	return diff,closest,cstring